#include "LinkTree.h"
#include <stdlib.h>
#include <stdio.h>
#define true 1
#define false 0

//创建节点
TNode *CreateTreeNode(ElementType element)
{
    TNode *newnode=(TNode*)malloc(sizeof(TNode));
    if(newnode==NULL)
    {
        printf("tree node malloc error\n");
        return NULL;
    }
    newnode->data=element;
    newnode->firstchild=NULL;
    newnode->nextsbiling=NULL;
    newnode->parent=NULL;
    return newnode;
}

//头插法连接
void ConnectBranch(TNode *parent, TNode *child)
{
    if(parent==NULL||child==NULL)
    {
        return;
    }
    child->nextsbiling=parent->firstchild;
    parent->firstchild=child;
    child->parent=parent;
}

void DisConnectBranch(TNode *parent, TNode *child)
{
    if(parent==NULL||child==NULL||parent->firstchild==NULL)
    {
        return;
    }
    if(parent->firstchild==child)
    {
        parent->firstchild=parent->firstchild->nextsbiling;
        child->parent=NULL;
        child->nextsbiling=NULL;
        return;
    }
    TNode *travelpoint=parent->firstchild;
    while(travelpoint->nextsbiling!=NULL)
    {
        if(travelpoint->nextsbiling==child)
        {
            travelpoint->nextsbiling=travelpoint->nextsbiling->nextsbiling;
            child->parent=NULL;
            child->nextsbiling=NULL;
        }
        travelpoint=travelpoint->nextsbiling;
    }
}

int InitLinkTree(LTree *tree)
{
    tree->root=CreateTreeNode("");
    if(tree->root==NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
}



void FreeNode(TNode *node)
{
    if(node==NULL)
        return;
    TNode *travelpoint=node->firstchild;
    while(travelpoint!=NULL)
    {
        TNode *next=travelpoint->nextsbiling;
        FreeNode(travelpoint);
        travelpoint=next;
    }
    free(node);
}
void FreeLinkTree(LTree *tree)
{
    FreeNode(tree->root);
    tree->root=NULL;
}

int GetLinkTreeHeight(TNode *node)
{
    if(node==NULL)
        return 0;
    else
    {
        int height=0;
        TNode *childpoint=node->firstchild;
        while(childpoint!=NULL)
        {
            int childheight=GetLinkTreeHeight(childpoint);
            height=height>childheight?height:childheight;
            childpoint=childpoint->nextsbiling;
        }
        return height+1;
    }
}

int GetChildCount(TNode *node)
{
    if(node==NULL)
        return 0;
    int count=0;
    TNode *travelpoint=node->firstchild;
    while(travelpoint!=NULL)
    {
        count++;
        travelpoint=travelpoint->nextsbiling;
    }
    return count;
}

void PrintTreeNode(TNode *node, int deepth)
{
    if(node==NULL)
    {
        return;
    }
        for(int i=0;i<deepth;i++)
        {
            printf("  |_");
        }
        printf("%s\n",node->data);
    TNode *child=node->firstchild;
    while(child!=NULL)
    {
        PrintTreeNode(child,deepth+1);
        child=child->nextsbiling;
    }
}

void TravelLinkTree(LTree *tree)
{
    PrintTreeNode(tree->root,0);
}

TNode *FindNode(TNode *node,ElementType data,int (*p)(ElementType,ElementType) )
{
    if(node==NULL)
    {
        return NULL;
    }
    if(p(node->data,data)&&node->parent!=NULL)
    {
        return node;
    }
    TNode *travelpoint=node->firstchild;
    TNode *targetnode=NULL;
    while(travelpoint!=NULL)
    {
        targetnode=FindNode(travelpoint,data,p);
        if(targetnode!=NULL)
        {
            return targetnode;
        }
        travelpoint=travelpoint->nextsbiling;
    }
    return targetnode;
}

TNode *CopyLinkTree(TNode *node)
{
    if(node==NULL)
    {
        return NULL;
    }
    TNode *newnode=CreateTreeNode(node->data);
    TNode *childnode=node->firstchild;
    while(childnode!=NULL)
    {
        TNode *newchildnode=CopyLinkTree(childnode);
        ConnectBranch(newnode,newchildnode);
        childnode=childnode->nextsbiling;
    }
    return newnode;
}